package Dynamic_programming;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @Description: 完全二叉树的插入数据：
 * @Param: $
 * @return: $
 * @Author 万家欣
 * @Date: 2022/7/25
 * Algorithm
 * @Version 1.0
 */
public class CBTInserter {
    private TreeNode p, q;
    private Queue<TreeNode> queue;
    public CBTInserter(TreeNode root) {
        this.p = root;
        this.queue = new ArrayDeque<>();
        this.queue.offer(root);

        findNextNode();
    }

    public int insert(int val) {
        int ret = q.val;
        TreeNode node  = new TreeNode(val);

        if (q.left == null) {
            q.left = node;
        } else {
            q.right = node;
            // update
            findNextNode();
        }

        queue.offer(node);

        return ret;
    }

    public TreeNode get_root() {
        return p;
    }

    public void findNextNode() {
        while (!this.queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.right == null) {
                this.q = node;
                if (node.left != null)
                    this.queue.offer(node.left);
                break;

            } else {
                this.queue.offer(node.left);
                this.queue.offer(node.right);
            }
        }
    }
}
